package ricky.quadtree
{
	/**
	 * 四叉树相关算法
	 * @author:pu
	 * @data:2011.5.9
	 */
	public class Morton
	{
		public function Morton()
		{
		}
		
		/**
		 * 得到morton码, 
		 * y行,x列 支持负数
		 */
		public static 	function morton(y:int,x:int):int
		{
			var isZero:Boolean=false;
			if(y<0)
			{
				y=Math.abs(y);
				isZero=true;
			}
			
			if(x<0)
			{
				x=Math.abs(x);
				isZero=true;
			}
			var m:int=y>x?y:x;
			
			var r:int=0;//结果
			var t:uint=0;//临时值
			var a:int=0;
			var al:int;
			while (m > 0) 
			{
				t=x&1;
				al=2*a;
				t<<=(al);
				x>>=1;
				r+=t;
				
				t=y&1;
				t<<=(al+1);
				r+=t;
				y>>=1;
				
				m>>=1;
				a++;
			}
			if(isZero)
				return -r;
			return r;
		}
		
		/**
		 * 得到morton码, 
		 * y行,x列
		 */
		public static 	function morton1(y:int,x:int):int
		{
			var m:int;
			if(y>=x)
				m=getBitLength(y);
			else
				m=getBitLength(x);		
			
			var r:int=0;//结果
			var t:uint=0;//临时值
			for(var a:uint=0;a<m;a++)
			{
				t=x&1;
				t<<=(2*a);
				x>>=1;
				r+=t;
				
				t=y&1;
				t<<=(2*a+1)
				r+=t;
				y>>=1;
			}
			return r;
		}

		/**
		 * 得到父节点
		 */
		public static function getParentMorton(morton:int):int
		{
			var mod:uint=morton % 4;
			if(mod==0)
				return morton;
			else
				return morton-mod;
		}
		
		/**
		 * 反转二进制代码
		 */
		public static function reversebit(z:int):int
		{
			var len:int=getBitLength(z);//得到长度
			
			var zy:int=0;//最终结果
			var zi:int=0;
			for(var x:uint=0;x<len;x++)
			{
				zi=z&1;
				z>>=1;				
				zy|=zi;
				if(x<len-1)
					zy<<=1;
			}
			return zy;
		}
		
		/**
		 * m码解码
		 * @param morton:uint 码
		 * 结果[行,列]
		 */
		public static function unMorton(morton:int):Array
		{
			var i:uint=0;
			var j:uint=0;
			var w:uint;
			var x:int=0;
			while(morton>0)
			{
				w=morton&1;
				morton>>=1;
				if(x % 2==0)
				{
					w<<=(x/2);
					j+=w;					
				}
				else
				{
					w<<=(x-1)/2;
					i+=w;	
				}
				x++;
			}
			
			return [i,j];
		}
		
		/**
		 * 得到整数位数
		 */
		public static function getBitLength(x:int):int
		{
			var l:int = 0;
			while (x > 0) {
				x >>= 1;
				l++;
			}
			return l;
		}
		
	}
}